package cn.orange.ch03_linked;

import cn.orange.ListNode;

/**
 * LC142.环形链表II
 给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null
 */
public class LC142 {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                fast = head;
                while (fast != slow) {
                    fast = fast.next;
                    slow = slow.next;
                }
                return slow;
            }
        }
        return null;
        /*if (fast == null || fast.next == null) {
            return null;
        }
        slow = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;*/
    }
    public static void main(String[] args) {
        LC142 alg = new LC142();
        ListNode na = new ListNode(1);
        ListNode nb = new ListNode(2);
        na.next = nb;
        nb.next = na;
        System.out.println(alg.detectCycle(na));
        ListNode n1 = new ListNode(6);
        ListNode n2 = new ListNode(8);
        n1.next = n2;
        ListNode n3 = new ListNode(0);
        n2.next = n3;
        ListNode n4 = new ListNode(-4);
        n3.next = n4;
        n4.next = n2;
        System.out.println(alg.detectCycle(n1));
    }
}
